Add Zeros题解

前言

刷cf的时候学到很多的一道题，倒不是说这个题出的多好，只是我跟着这个题的题解学到了很多c++新标准的语法之类的内容。

题目描述

You’re given an array a initially containing nn integers. In one operation, you must do the following:

Choose a position $i$ such that 1<i≤|a| and a_i=|a|+1−i, where |a| is the current size of the array.
Append i−1 zeros onto the end of a.

After performing this operation as many times as you want, what is the maximum possible length of the array $a$?

思路

这个题的思路其实不是很难，只是题目本身有点绕，实际上只要根据题意建图后跑dfs就好，不过有很多细节需要处理。

注意`a_i的数量级为1e14

代码

虽然跟着std精简了很多我的代码，可是结果还是很丑，不如在std的基础上补充细节：

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
        int n;
        cin >> n;
        vector<ll> A(n);
        for (int i = 0; i < n; i++) cin >> A[i];
        map<ll,vector<ll>> adj;	// 使用vector不方便建图（第一维太大，1e14）
        for (int i = 1; i<n; i++) {
            ll u = A[i] + i;
            ll v = u + i;
            adj[u].push_back(v);
        }
        set<ll> vis;	// 不能使用bool数组，因为未离散化的数组下标很大
        function<void(ll)> dfs = [&](ll u) -> void {	// lambda函数
            if (vis.count(u)) return;
            vis.insert(u);
            for (ll v : adj[u]) dfs(v);
        };
        dfs(n);
        cout << *vis.rbegin() << "\n";	// 使用*rbegin()找到set末尾元素，也就是可以访问到的最大长度
  }
  return 0;
}

lambda表达式

其实这东西对我来说并不算陌生，我在python和matlab中偶尔会用到这东西，在c++也阅读过jiangly大佬的代码。我很喜欢这种简洁清晰的表达方式，不过从未在c++中编写过带lambda函数的程序。

格式

1	[capture](parameter_list) -> return_type { body }

capture: 捕获外部变量的方式，可以通过值捕获、引用捕获等。
parameter_list: 参数列表，和普通函数一样，可以为空或包含多个参数。
return_type: 返回类型，可以省略，编译器会自动推断。
body: 表达式体，函数的实现部分。

捕获外部变量

[ ] 不捕获任何变量。
[x] 按值捕获变量x。
[&] 按引用捕获所有外部变量。
[=] 按值捕获所有外部变量。
[this] 捕获当前对象的指针，允许在lambda中访问成员变量和成员函数。

这个题中若是使用[]则不能在dfs函数中访问vis，如果用[=]则不能对vis产生实际修改。

返回类型

可以不填，编译器会进行推导。

递归

lambda函数不能直接调用自己，不过可以通过其他方式实现递归

std::function<void(ll)>
c++14auto&& self实现自引用

对于第一个方法，std中的dfs就是用这种方式实现递归，其中void(ll)为函数类型，即返回值为空，参数类型为ll。

对于第二种方法：

auto dfs = [&](auto &&self, long long u) -> void {
    if(vis.count(u)) return; 
    vis.insert(u);
    for(long long v : adj[u]) self(self, v);
};
dfs(dfs, n);

这段代码通过auto&& self实现了自引用，每次调用函数需要额外添加self参数。

ChatGPT-4o:

性能差异：自引用递归 lambda 通常比 std::function 递归更高效，因为它避免了类型擦除、内存分配和间接调用的开销。

灵活性：std::function 提供更高的灵活性，因为它可以封装任何符合签名的可调用对象（包括函数、lambda 和函数对象），而自引用递归 lambda 更适用于递归的场景。

搭配stl

其实与这个题目无关，不过经常使用sort定义cmp函数时可以在函数内写lambda表达式：

1
2
3

sort(arr.begin(), arr.end(), [](const Node &a, const Node &b) {
    return a.id < b.id;
});

除了sort，其他很多stl库中的函数也可以用lambda表达式来精简参数，使代码更简洁好看。

STL使用

我从初中开始打noip时就非常热爱stl，对现成的函数和数据结构爱不释手。

但是有的时候阅读这些题解才发现我对stl的使用并不优雅，至少打眼一看，代码里全是固定MAXN大小的数组。

这道题可以看出的可以借鉴的stl写法：

使用vector代替数组
使用set代替bool数组 / 哈希（毕竟可以用stl谁愿意手搓呢）
使用map解决下标范围广的存图问题
使用*rbegin()而不是额外定义变量获取最大值

STL的用法想先鸽一下，等之后在专门写博客整理汇总。